In the process of moving data over a network, it is necessary to determine whether the data will be allowed on the network, and if so, where the data will be directed. When the data is sent from a source to a destination, the network may determine if both the sender and the recipient are valid and permitted to use the network, as well as how the data will be processed. Transport Control Protocol/Internet Protocol (TCP/IP) data is typically transferred by means of frames that include at least two components, an address header and a data payload. Information that is typically used to move the data through the network to the destination may be found in the address header in the form of a five-tuple that comprises following fields: a source address, a destination address, a source port, a destination port and a protocol.
It is not to unusual to have a network addressing scheme that supports as many as 4 billion sources having the ability to send data to any of 4 billion destinations and where each source or destination can have upwards of 64 thousand ports. Thus, trying to support such an addressing scheme may require an enormously large look-up table, as well as a traffic management system with a staggering amount of memory. On the other hand, the presence of a limited amount of traffic on a network at any given time allows the use of a smaller table that includes a lesser amount of information. To accomplish this, a hash function may be used on the pertinent information in the address header to determine an index value into the smaller table.
A hash function is a mathematical algorithm that is capable of mapping values from a substantially large domain to a smaller one. A “good” hash function includes those, in which the application of the hash function to a large set of values results in a smaller set of index values that are evenly distributed in the smaller domain. A “bad” hash function would be one, in which many of the values in the set from the larger domain are mapped into the same index value of the smaller domain. Any such occurrence is typically referred to as a collision. Because only a single connection can physically reside as an entry at any particular index value, any collision requires that additional information be kept in each table entry to further instruct the network where to look for any additional connections that hashed to the same index value. This chaining of entries that have the same index values requires a processing engine to hash to an index value, read out the entry, compare it to a pre-hashed five-tuple, and if a match is not found to use a pointer in the entry to read another entry. This procedure is repeated until either there is a match or the last entry in a chain is reached, reducing the efficiency of the processing engine because of the repetitive procedure being performed on every data packet.
Therefore, there is a need in the industry for an apparatus, method and system for managing network traffic through the use of an improved hash function. Thus, it is with respect to these considerations, and others, that the present invention has been made.